Heap

👉 본 포스트는 자료구조의 개념에 추가적으로, 직접적인 C++ 구현을 통한 명확한 자료구조 이해를 위해 작성되었습니다. 👈

우선순위 큐를 이해하기 위해선 Heap 자료구조를 명확하게 이해하여야만 한다.

우리는 많은 알고리즘 문제에서 우선순위 큐를 사용해본 적이 있다. BFS 알고리즘 뿐 만 아니라 다양한 우선순위, 스케쥴링 알고리즘에도 우선순위 큐는 빠지지 않고 사용된다.

우선순위 큐의 경우 느슨한 정렬 형태의 Heap 자료구조를 통해 효과적으로 특정 기준에 의한 정렬값들을 차례로 추출해낼 수 있다.

Complete Binary Tree

Heap은 완전 이진 트리 형태를 가지고 있다.

Complete Binary Tree(완전 이진 트리) : 마지막 레벨을 제외한 모든 레벨은 모든 노드가 채워져 있고, 마지막 레벨의 노드들은 왼쪽부터 차례로 채워져 있는 트리 형태

Full Binary Tree(포화 이진 트리) : 자식 노드를 아예 가지지 않거나, 무조건 2개를 가지는 이진 트리 형태

Min Heap : 부모 키 값이 자식 노드 키 값보다 작은 완전 이진 트리, 루트 노드가 트리 상에서 가장 작은 값이다.

Max Heap : 부모 키 값이 자식 노드 키 값 보다 큰 완전 이진 트리, 루트 노드가 트리 상에서 가장 큰 값이다.

Heap 삽입, 삭제 연산

삽입

1. 완전 이진 트리의 다음으로 비워져 있는 노드에 값을 삽입.
2. 삽입한 노드의 부모 노드와 값을 비교해 조건에 맞지 않을 경우 swap 해줌
3. 루트 노드에 도달하거나, 더 이상 조건에 맞지 않는 노드가 없을 때 까지 1, 2번 과정 반복

삭제 -> 삭제에 앞서 Heap은 루트 노드의 원소만을 삭제할 수 있음(pop)

1. 루트 노드 원소 삭제
2. 마지막에 위치한 노드를 루트 노드 위치로 끌어올림
3. 이동시킨 루트 노드와 자식노드의 값을 비교해가며 조건에 맞지 않을 경우 swap 해줌
4. 최하단 레벨의 노드까지 도달했거든 더 이상 조건에 맞지 않는 노드가 없을 때까지 swap 과정 반복

구현 코드

-> STL Library의 min heap 우선순위 큐와 유사하게 구현하려 시도한 코드이다.

#include <iostream>

#define SIZE 10000

using namespace std;

class MinHeap {
public :
    int *heap = new int[SIZE];
    int heapcount = 1;

    void swap(int *a, int *b) {
        int temp = *a;
        *a = *b;
        *b = temp;
    }

    int size() {
        return heapcount - 1;
    }

    bool isEmpty() {
        return heapcount == 1;
    }

    int top() {
        return heap[1];
    }

    void push(int num) {
        int curidx = heapcount;
        heap[heapcount++] = num;

        while (curidx > 1 && heap[curidx] < heap[curidx / 2]) {
            swap(&heap[curidx], &heap[curidx / 2]);
            curidx /= 2;
        }
    }

    void pop() {
        heap[1] = heap[--heapcount];

        int parent = 1, child = 2;
        if (child + 1 <= heapcount)
            child = (heap[child] > heap[child + 1]) ? child + 1 : child;

        while (child <= heapcount && heap[child] < heap[parent]) {
            swap(&heap[child], &heap[parent]);
            parent = child;
            child *= 2;
            if (child + 1 <= heapcount)
                child = (heap[child] > heap[child + 1]) ? child + 1 : child;
        }
    }
};


int main() {
    int tc, n, input;
    MinHeap minheap;

    cin >> tc;
    while (tc--) {
        cin >> n;
        while (n--) {
            cin >> input;
            minheap.push(input);
        }

        while (!minheap.isEmpty()) {
            cout << minheap.top() << ' ';
            minheap.pop();
        }
        cout << '\n';
    }

    return 0;
}